#include <vector>
#include <unordered_map>


using namespace std;

class RandomizedSet {
public:
    RandomizedSet() = default;
    
    /**
     * 插入思路
     * 1. 如果 val 已存在 返回 false
     * 2. 否则 将 val 加到 vector 末尾
     * 3. 在 map 中记录 val 的索引
     * 4. 返回 true
     */
    bool insert(int val) {
        if (map.count(val)) {
            return false;
        }
        v.push_back(val);
        map[val] = v.size() - 1;
        return true;
    }
    
    /**
     * 删除思路
     * 1. 如果 val 不存在 返回 false
     * 2. 否则 找到 val 的索引
     * 3. 用 vector 最后一个元素覆盖 val 的位置
     * 4. 更新最后一个元素在 map 中的索引
     * 5. 删除 vector 最后一个元素
     * 6. 从 map 中删除 val
     * 7. 返回 true
     */
    bool remove(int val) {
        if (!map.count(val)) {
            return false;
        }
        int index = map[val];
        int last_element = v.back();
        
        v[index] = last_element;
        map[last_element] = index;
        
        v.pop_back();
        map.erase(val);
        
        return true;
    }
    
    /**
     * 随机获取思路
     * 1. 生成一个随机索引
     * 2. 返回该索引在 vector 中对应的元素
     */
    int getRandom() {
        int random_index = rand() % v.size();
        return v[random_index];
    }

private:
    vector<int> v;
    unordered_map<int, int> map;
};